package BinaryTree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static  class  TreeNode{
        public char val;//数据域
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用
        public TreeNode(char val){
            this.val =val;
        }
    }
    public TreeNode creatTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right =E;
        C.left = F;
        C.right =G;
        E.right = H;
        return A;
    }
    //前序遍历
    public void PreOder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        PreOder(root.left);
        PreOder(root.right);
    }
    //oj题
    //给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

    //遍历思路
   // List<Character> list = new ArrayList<>();
    /*public List<Character> preorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return  list;
    }*/
    //子问题
    public List<Character> preorderTraversal2(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
       List<Character> leftTree=preorderTraversal2(root.left);
       list.addAll(leftTree);
       List<Character> rightTree =preorderTraversal2(root.right);
       list.addAll(rightTree);
       return list;

    }
    //中序遍历
    public void InOder(TreeNode root){
        if(root==null){
            return;
        }
        InOder(root.left);
        System.out.print(root.val+" ");
        InOder(root.right);
    }

    //遍历思路
    /*public  List <Character> list =new ArrayList<>();
    public List<Character> inorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }*/
    //子问题
   /* public List<Character> inorderTraversal2(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        List<Character> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Character> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }*/

    //后序遍历
    public void PostOder(TreeNode root){
        if(root==null){
            return;
        }
        PostOder(root.left);
        PostOder(root.right);
        System.out.print(root.val+" ");
    }
    //遍历思路
    public List<Character> list =new ArrayList<>();
    public List<Character> postorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return  list;
    }
    //子问题
    public List<Character> postorderTraversal2(TreeNode root) {
        List<Character> list =new ArrayList<>();
        List <Character> leftTree = postorderTraversal2(root.left);
        list.addAll(leftTree);
        List<Character> rightTree = postorderTraversal2(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;

    }
    //获取树中节点的个数
    public static  int nodeSize =0;
    //遍历二叉树，只要根节点不为空
    public void size(TreeNode root){
        if(root==null){
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    //子问题 ：整棵树有多少个节点 = 左子树的节点 +右子树节点 +1
    public int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        return size2(root.left )+size2(root.right)+1;
    }


    /*什么是叶子
    root.left==null&&root.right==null
    整棵树的叶子节点 = 左子树的叶子+右子树的叶子
     */
    // 获取叶子节点的个数
    //遍历思路
    public static  int leafSize =0;
    public void getLeafNodeCount(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    //子问题思路
    public int getLeafNodeCount2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }
    //获取K层的节点个数
    public int getKLevelNodeCount(TreeNode root,int k){
        /* k=3 ,
        root左树的k-1层+右树的k-1层

         */
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    //获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
        //return leftHeight>rightHeight ? leftHeight+1 : rightHeight+1;
    }

   /* 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    */
   public boolean isSameTree(TreeNode p, TreeNode q) {
       //1判断结构是否一样
       if(p!=null && q==null||p==null&&q!=null){
           return false;
       }
       if(p==null&&q==null){
           return true;
       }
       //2.判断值是否一样
       if(p.val!=q.val){
           return false;
       }
       return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
   }
}
